The present invention provides a way for people, particularly persons with visual disabilities, to be able to navigate in indoor spaces, particularly spaces that do not have GPS coverage and places where no detailed maps have been created. Such an invention is needed because confusion, being lost, and losing track of one's orientation within large or unfamiliar indoor spaces are some of the biggest challenges facing people with blindness and low vision. Various techniques for remembering directions and locations can be learned to minimize these issues, but people who cannot readily access visual information are still at a significant disadvantage, even for getting around in places where sighted individuals can navigate visually. Many blind individuals avoid venturing into unfamiliar territory unless absolutely necessary. Thus, persons with visual disabilities are often deprived of many everyday life opportunities available to people without such disabilities.
Since GPS typically doesn't work indoors and isn't fine-grained enough for the purpose, other technology for indoor wayfinding has recently been introduced, taking advantage of ubiquitous smartphone capabilities. Most notably, WiFi- and Bluetooth beacon systems have been developed for the consumer market to enable navigation in large indoor spaces (for example, airports) and to find products in retail chain stores. Several groups are working on adaptations for users with visual disabilities. However, there are a number of costly disadvantages of this technology that undermine its potential for general, everyday use:                Indoor spaces must be mapped out in detail to create an electronic map for the navigation app to use. Databases must be also be created to allow a conversion of received beacon signal strengths to locations on the map.        For Bluetooth- or tag-based navigation products, the building must also be outfitted with customized beacon or electronic tag hardware.        Although private entities may one day invest in these mapping and hardware-installation tasks for the fraction of large buildings and facilities where the demand for such services is great among people without disabilities, it is unlikely to be undertaken for smaller venues such as restaurants, schools, medical offices, and private residences, where non-visually-impaired people do not require such technology.        
Most traditional route planning systems assume the existence of an accurate map that represents the possible routes that can be taken by the user, for example, in a conventional GPS navigation system, the user's position is provided by GPS measurements and a map containing roads, highways, and addresses is used for generating the route. Most route planning systems use a search technique based on some kind of cost function, in which route segments are added to potential route plans, the relative desirability of each determined by a cost function. The well-known A* (pronounced “A star” algorithm (see Barr, Avron, and Edward Feigenbaum, “The Handbook of Artificial Intelligence, Vol. 1”, William Kaufmann, Inc., 1981, pp. 64-73) or one of its variants is typically used to efficiently find a route solution with the best or close-to-best cost. The cost function may simply be the expected time to complete the travel, the distance of the route, or a combination of such factors. Costs associated with distance and fuel usage can be applied to choose the most effective route for the user. Other techniques are described to choose the most effective route, such as U.S. Pat. No. 9,476,724 to Caine et al, which discloses the use of familiarity scores that describe the familiarity or popularity of route segments, and weighting the generation of a plan accordingly. Another technique is shown in U.S. Pat. No. 9,857,187 to Profous et al, which discloses the use of a reachability metric to guide the search.
Some systems provide techniques for going beyond the boundaries of roads, for example U.S. Pat. No. 9,671,238 to Hoogland discloses a system that can generate routes that transition from terrestrial roads to non-road travel, such as water or air travel, and back. However, such approaches still require the use of predefined maps or map-like structures that show the connectivity between the various points that can be navigated during travel from the starting point to the destination.
The above prior art, however, does not address problems associated with incomplete maps or maps with high uncertainties in the location of the route elements, such as hypothesizing a possible route segment to follow between two route segments, or the possibility that two points represented on a map might actually be the same point in reality if uncertainties in the map position data are taken into account.
There are inventions, however, that address the more extreme case that no map data at all is available. In such cases, previous systems have used the process of traveling between waypoints or following breadcrumbs. For example, U.S. Pat. No. 9,829,335 to Chang et al discloses a virtual breadcrumb approach for indoor navigation. A position sensor measures the position of the user and stores the position for later recall. A series of waypoints with a distance-related value, such as steps and direction taken is stored with each. After traveling the path, the user can then command the system to guide him or her back along the waypoints to the starting point, using various sensor techniques to assure proper path following. This approach is good for following a specific path backwards or forwards, but does not correct for inefficiencies in the stored path. For example, if the user becomes slightly lost and wanders through an area that was not necessary for reaching the goal, the breadcrumbs would guide the person to follow the unnecessary as well as necessary parts of that path when returning to the starting point. Chang et al also does not disclose provisions for sharing parts of multiple paths taken at different previous points, which would be helpful for navigating in a complex environment. U.S. Patent Application US 2010/0268454 by Fountain discloses waypoint navigation in an unconstrained three-dimensional space, such as in underwater or wilderness environments, but similarly does not address the issues related to finding an optimal path given complex or overlapping recorded paths. The prior art also does not address the problems of uncertainties in both user position and path position that cause various ambiguities in the exact direction the user should turn, and can therefore yield very confusing navigation instructions if the user is not at the center of the probability region calculated by the system.
In the conventional GPS navigation scenario, the position of the user is known to a relatively high accuracy relative to the accuracy of the associated outdoor navigation maps. For example, a GPS location may be known to 15 feet or better, whereas the distances between roads is typically a much greater distance, so in typical vehicular navigation problems, the accuracy in user position is not a major problem. However, when GPS signals are not available, or for indoor navigation where much higher accuracy may be required, uncertainties in the user position become important and may even be larger in magnitude than some of the distances being traversed. Because of this, certain aspects of the uncertainty in user position have been addressed in the prior art.
U.S. Pat. No. 9,880,008 to Wei discloses the use of a distance sensor and a map of the interior of a building to correct for the errors in using a dead-reckoning inertial position sensor. The distance to walls in the building is matched with the known map of the building to calculate a more likely position that the user is actually located. However, this approach requires an additional distance sensor and an accurate and detailed map of the building. U.S. Pat. No. 9,797,732 to Li et al discloses the use of a map to improve the error bounds in position estimation. As the user traverses an indoor space, the path is compared to the constraints in the map, such as walls and other non-traversable areas and adjusts the location of the points to cause the path to fall within a physically-possible route. U.S. Pat. No. 9,326,103 to Shen et al discloses the use of magnetic field anomalies in addition to RF signals to obtain characteristic signatures from various parts of an indoor venue, so as to estimate the position of the user. These approaches require an accurate predefined map, which will not be available for many indoor environments.
U.S. Pat. No. 9,746,327 to Hakim et al, discloses a technique that requires less detailed map information, which is to take the user position obtained by dead reckoning, which is subject to drift and other errors, and improve it based on identifying known features or constraints in the environment. A priori known constraints, such as characteristics of the building the user is in, can be combined with features such as stairways, to help localize where the user is located. Hakim et al also discloses using known absolute location information, such as a GPS reading, to propagate positional corrections and thus correct previous positions of a stored path. This prior art also shows techniques for matching encountered features to similar features found earlier, but does not address the problem of uncertainty about whether a particular feature is the same or possibly different example of the same feature type. For example, the stair case example illustrated in Hakim et al is a case where likelihood of finding a second, different staircase nearby is low, but an important case such as doorways is not addressed in the prior art, where it would cause significant errors to assume that a previously-encountered nearby door is surely the doorway in question.
U.S. Pat. No. 9,568,587 to Faragher et al discloses an approach for tracking a person using particle filters. That system updates the position of the person based on inertial measurements, which are then adjusted and improved by radio signal strengths. The user's position can be determined, for example, by a weighted average of the particles in the particle filters, which can also be viewed as a distribution of the possible locations of the user.